#include <iostream>
#include <vector>

using namespace std;

// 121.三角形最小路径和
// 给定一个三角形 triangle ，找出自顶向下的最小路径和

// 动态规划
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        vector<int> mini = triangle[triangle.size() - 1];
        for(int i = triangle.size() - 2; i >= 0; --i)   // 从倒数第二层开始
            for(int j = 0; j < triangle[i].size(); ++j)
                mini[j] = triangle[i][j] + min(mini[j], mini[j+1]);

        return mini[0];
    }
};
int main() {

    vector<vector<int>> triangle = { {2},
                                     {3,4},
                                     {6,5,7},
                                     {4,1,8,3}};
    cout << Solution().minimumTotal(triangle) << endl;
    // 11
    return 0;
}
